package myself.a001算法入门;

import myself.a000util.Logarithm;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/20
 * Time 21:15
 * Mail 739153436@qq.com
 */
public class BinarySearch {
    public static void main(String[] args) {
        // Logarithm.BS.checkBSExit(BinarySearch.class,"BSExit");
        // Logarithm.BS.checkBSLeft(BinarySearch.class,"BSNearLeft");
        Logarithm.BS.checkBSRight(BinarySearch.class, "BSNearRight");
    }

    // 查找是否存在某个数
    public boolean BSExit(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > num) {
                right = mid - 1;
            } else if (arr[mid] < num) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    // 在arr上，找满足>=value的最左位置
    public int BSNearLeft(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] >= num) {
                index = mid;
                right = mid - 1;
            } else if (arr[mid] < num) {
                left = mid + 1;
            }/* else {
                return mid;
            }*///之前错误代码，没有考虑连续两个数相等的情况，可能会把右边的数先拷贝出来，如：-5，-5，-5，1，2，3
        }
        return index;
    }

    // 在arr上，找满足<=value的最右位置
    public int BSNearRight(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > num) {
                right = mid - 1;
            } else if (arr[mid] <= num) {
                index = mid;
                left = mid + 1;
            }/* else {
                return mid;
            }*///之前错误代码，没有考虑连续两个数相等的情况，可能会把右边的数先拷贝出来，如：-5，-5，-5，1，2，3
        }
        return index;
    }

    public void BSAwesome(int[] arr, int num) {

    }
}
